#pragma once

#include <string>
#include <stack>
#include <map>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <list>
#include <memory>
#include <iostream>
#include <sstream>

using namespace std;

namespace FiniteAutomata
{
	class RegExInput
	{
	public:
		char ReadNextChar();
		char PeakNextChar();
	};

	// Regular expression operators. The numeric values of these enum values are used
	// for determining precedence. So please keep the order.
	enum Operator { Invalid, Star, Concat, Union, LeftParen, RightParen };

	class State;

	typedef multimap<char, shared_ptr<State>> Transitions;

	class State
	{
		friend class NondeterministicFiniteAutomaton;
		friend class Parser;

	public:
		Transitions transitions;

	public:
		State()
		{
		}

		virtual ~State()
		{
		}

		void AddTransition(pair<char, shared_ptr<State>> transition)
		{
			transitions.insert(transition);
		}

		void AddTransition(char input, shared_ptr<State> state)
		{
			transitions.insert(make_pair(input, state));
		}
	};

	typedef deque<shared_ptr<State>> TransitionTable;

	class NondeterministicFiniteAutomaton
	{
		friend class Parser;
	protected:
		TransitionTable transitionTable;
	public:
		void AssignStateIDs();

#ifdef _DEBUG
	public:
		void Dump()
		{
			int id = 0;
			map<shared_ptr<State>, int> stateIdMapping;
			for (TransitionTable::const_iterator s = transitionTable.cbegin(); s != transitionTable.cend(); s++)
			{
				stateIdMapping.insert(make_pair(*s, id++));
			}

			for (TransitionTable::const_iterator s = transitionTable.cbegin(); s != transitionTable.cend(); s++)
			{
				shared_ptr<State> state = (*s);

				cout << "[State " << stateIdMapping[state] << "]" << endl;
				cout << "Transitions: " << endl;

				for (Transitions::const_iterator t = state->transitions.cbegin(); t != state->transitions.cend(); t++)
				{
					if (t->first == 0)
						cout << "{e}";
					else
						cout << t->first;

					cout << "->" << stateIdMapping[t->second];
					cout << endl;
				}
			}
		}
#endif
	};

	class DeterministicFiniteAutomaton : public NondeterministicFiniteAutomaton
	{
		set<shared_ptr<State>> acceptingStates;
	};

	class Canvas
	{
	public:
		void Clean();
	};

	class Parser
	{
	protected:
		Canvas canvas;
		stack<TransitionTable> transitionTableStack;
		stack<Operator> operatorStack;

	public:
		Parser()
		{}

		~Parser()
		{}

		NondeterministicFiniteAutomaton CreateNFA(string s);
		DeterministicFiniteAutomaton ConvertNFAtoDFA(NondeterministicFiniteAutomaton nfa);

	protected:
		shared_ptr<State> CreateNewState()
		{
			return shared_ptr<State>(new State);
		}

		Operator ToOperator(char ch)
		{
			switch (ch)
			{
			case '*':
				return Operator::Star;
			case '|':
				return Operator::Union;
			case '(':
				return Operator::LeftParen;
			case ')':
				return Operator::RightParen;
			}
			return Operator::Invalid;
		}

		bool IsOperator(char ch)
		{
			return ToOperator(ch) != Operator::Invalid;
		}

		void AddTransition(shared_ptr<State>, char, shared_ptr<State>);
		void FromSingleChar(char ch);
		void Eval();
		void Concat();
		void Star();
		void Union();

		set<shared_ptr<State>> EpsilonClosure(const set<shared_ptr<State>> states);
		set<shared_ptr<State>> Move(char ch, set<shared_ptr<State>> states);

		//! Converts NFA to DFA using the Subset Construction Algorithm
		void ConvertNFAtoDFA();

		//! Optimizes the DFA
		/*! This function scanns DFA and checks for states that are not
		accepting states and there is no transition from that state
		to any other state. Then after deleting this state we need to
		go through the DFA and delete all transitions from other states
		to this one.
		*/
		void ReduceDFA();
	};

	class ParsingException : exception
	{
	public:
		ParsingException()
		{
		}

		int location;
		string message;

	protected:
		virtual const char* what() const throw()
		{
			stringstream s;
			s << "Parsig error at " << location << " : " << message;
			string result;
			s >> result;
			return result.data();
		}
	};
}